/**
 * HexGridUtils.java
 *
 * Roslan's Remake of MOO in 3D using Ardor3D
 * (C) 2011 Roslan Amir. All rights reserved.
 */

package com.roslan.games.moo3d.utils;

import java.awt.Point;

import com.ardor3d.math.FastMath;
import com.ardor3d.math.MathUtils;

/**
 * Comments go here.
 * 
 * @author Roslan Amir
 * @version 1.0 - Jan 5, 2011
 */
public class HexGridUtils {
	/**
	 * 
	 */
	public static final double HEXGRID_S = 1.0;

	/**
	 * 
	 */
	public static final double HEXGRID_H = FastMath.sin(30 * MathUtils.DEG_TO_RAD) * HEXGRID_S;

	/**
	 * 
	 */
	public static final double HEXGRID_R = FastMath.cos(30 * MathUtils.DEG_TO_RAD) * HEXGRID_S;

	/**
	 * 
	 */
//	public static final double HEXGRID_A = HEXGRID_R * 2;

	/**
	 * 
	 */
//	public static final double HEXGRID_B = HEXGRID_S + HEXGRID_H * 2;

	/**
	 * Returns the origin in world coordinates for the grid tile given the hex coordinates (x,y).
	 * 
	 * @param x - the x coordinate
	 * @param y - the y coordinate
	 * @param tuple - the array to store the result in. If null, a new array is created and returned.
	 * @return the vector for the origin
	 */
	public static double[] getHexWorldOrigin(double x, double y, double[] tuple) {
		if (tuple == null)
			tuple = new double[2];
		tuple[0] = (x - y) * HEXGRID_R;
		tuple[1] = (x + y) * (HEXGRID_S + HEXGRID_H);
		return tuple;
	}

	/**
	 * Returns the origin in world coordinates for the grid tile given the hex coordinates (x,y).
	 *
	 * @param tile - the coordinates
	 * @param tuple - the array to store the result in. If null, a new array is created and returned.
	 * @return the vector for the origin
	 */
	public static double[] getHexWorldOrigin(Point tile, double[] tuple) {
		return getHexWorldOrigin(tile.x, tile.y, tuple);
	}

	/**
	 * Return the array of vertices to draw the full hex.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return the array of line segments
	 */
	public static double[][] getAllSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[6][2];
		tuples[0][0] = 0;			tuples[0][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		tuples[1][0] = - HEXGRID_R;	tuples[1][1] = - HEXGRID_S / 2;
		tuples[2][0] = - HEXGRID_R; tuples[2][1] = HEXGRID_S / 2;
		tuples[3][0] = 0;			tuples[3][1] = HEXGRID_S / 2 + HEXGRID_H;
		tuples[4][0] = HEXGRID_R;	tuples[4][1] = HEXGRID_S / 2;
		tuples[5][0] = HEXGRID_R;	tuples[5][1] = - HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Return the array of vertices to draw the lower-right, lower-left and left 3-line segments of a hex grid.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return the array of line segments
	 */
	public static double[][] getLowerRightLowerLeftLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[4][2];
		tuples[0][0] = HEXGRID_R;	tuples[0][1] = - HEXGRID_S / 2;
		tuples[1][0] = 0;			tuples[1][1] = - HEXGRID_S / 2 - HEXGRID_H;
		tuples[2][0] = - HEXGRID_R; tuples[2][1] = - HEXGRID_S / 2;
		tuples[3][0] = - HEXGRID_R; tuples[3][1] = HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Return the array of vertices to draw the upper-right and right 2-line segments of a hex grid.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return the array of line segments
	 */
	public static double[][] getUpperRightRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = 0;			tuples[0][1] = HEXGRID_S / 2 + HEXGRID_H;
		tuples[1][0] = HEXGRID_R;	tuples[1][1] = HEXGRID_S / 2;
		tuples[2][0] = HEXGRID_R;	tuples[2][1] = - HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getLowerLeftLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = 0;			tuples[0][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		tuples[1][0] = - HEXGRID_R; tuples[1][1] = - HEXGRID_S / 2;
		tuples[2][0] = - HEXGRID_R; tuples[2][1] = HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getLeftUpperLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = - HEXGRID_R; tuples[0][1] = - HEXGRID_S / 2;
		tuples[1][0] = - HEXGRID_R; tuples[1][1] = HEXGRID_S / 2;
		tuples[2][0] = 0;			tuples[2][1] = HEXGRID_S / 2 + HEXGRID_H;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getUpperLeftUpperRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = - HEXGRID_R; tuples[0][1] = HEXGRID_S / 2;
		tuples[1][0] = 0;			tuples[1][1] = HEXGRID_S / 2 + HEXGRID_H;
		tuples[2][0] = HEXGRID_R;	tuples[2][1] = HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getRightLowerRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = HEXGRID_R;	tuples[0][1] = HEXGRID_S / 2;
		tuples[1][0] = HEXGRID_R;	tuples[1][1] = - HEXGRID_S / 2;
		tuples[2][0] = 0;			tuples[2][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getLowerRightLowerLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[3][2];
		tuples[0][0] = HEXGRID_R;	tuples[0][1] = - HEXGRID_S / 2;
		tuples[1][0] = 0;			tuples[1][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		tuples[2][0] = - HEXGRID_R;	tuples[2][1] = - HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Return the array of vertices to draw the right 1-line segment of a hex grid.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return the array of line segments
	 */
	public static double[][] getRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = HEXGRID_R;	tuples[0][1] = HEXGRID_S / 2;
		tuples[1][0] = HEXGRID_R;	tuples[1][1] = - HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Return the array of vertices to draw the upper-left 1-line segment of a hex grid.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return the array of line segments
	 */
	public static double[][] getUpperLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = - HEXGRID_R;	tuples[0][1] = HEXGRID_S / 2;
		tuples[1][0] = 0;			tuples[1][1] = HEXGRID_S / 2 + HEXGRID_H;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getLowerRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = HEXGRID_R;	tuples[0][1] = - HEXGRID_S / 2;
		tuples[1][0] = 0;			tuples[1][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getLowerLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = 0;			tuples[0][1] = - (HEXGRID_S / 2 + HEXGRID_H);
		tuples[1][0] = - HEXGRID_R;	tuples[1][1] = - HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @return
	 */
	public static double[][] getUpperRightSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = 0;			tuples[0][1] = HEXGRID_S / 2 + HEXGRID_H;
		tuples[1][0] = HEXGRID_R;	tuples[1][1] = HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Comment for method.
	 * 
	 * @param tuples - the array to store the result in. If null, a new array is created and returned.
	 * @param tuples
	 */
	public static double[][] getLeftSegmentVertices(double[][] tuples) {
		if (tuples == null)
			tuples = new double[2][2];
		tuples[0][0] = - HEXGRID_R; tuples[0][1] = - HEXGRID_S / 2;
		tuples[1][0] = - HEXGRID_R; tuples[1][1] = HEXGRID_S / 2;
		return tuples;
	}

	/**
	 * Calculate the distance (in integral value) between the two tiles.
	 * 
	 * @param fromX - the x-coordinate of the starting grid tile
	 * @param fromY - the y-coordinate of the starting grid tile
	 * @param toX - the x-coordinate of the ending grid tile
	 * @param toY - the y-coordinate of the ending grid tile
	 * @return the distance between the two tiles with the distance between 2 adjacent tiles defined as 1
	 */
	public static int distance(int fromX, int fromY, int toX, int toY) {
		int dx = toX - fromX;
		int dy = toY - fromY;
		if ((dx & 0x80000000) != (dy & 0x80000000))
			return Math.max(Math.abs(dx), Math.abs(dy));
		else
			return Math.abs(dx) + Math.abs(dy);
	}

	/**
	 * Calculate the distance (in integral value) between the two tiles.
	 * 
	 * @param from - the coordinates of the starting grid tile
	 * @param to - the coordinates of the ending grid tile
	 * @return the distance between the two tiles with the distance between 2 adjacent tiles defined as 1
	 */
	public static int distance(Point from, Point to) {
		int dx = to.x - from.x;
		int dy = to.y - from.y;
		if ((dx & 0x80000000) != (dy & 0x80000000))
			return Math.max(Math.abs(dx), Math.abs(dy));
		else
			return Math.abs(dx) + Math.abs(dy);
	}

	/**
	 * Returns the list of hex coordinates for the path between the starting hex and the ending hex. The list does not include
	 * the starting hex coordinates.
	 * 
	 * @param startX - the starting hex x-coordinate
	 * @param startY - the starting hex y-coordinate
	 * @param endX - the ending hex x-coordinate
	 * @param endY - the ending hex y-coordinate
	 * @return the array of <code>Point</code>s representing the coordinates for the hexes along the way
	 */
	public static Point[] path(int startX, int startY, int endX, int endY) {
		/*
		 * Returns if start and end nodes are the same
		 */
		if (startX == endX && startY == endY) {
			return null;
		}

		final Point[] pathList = new Point[distance(startX, startY, endX, endY)];

		/*
		 * along diagonal axis (lower-left to upper-right or vice-versa)
		 */
		if (startY == endY) {
			int index = 0;
			if (startX < endX) { // lower-left to upper-right
				for (int x = startX + 1; x < endX; x++) {
					pathList[index++] = new Point(x, startY);
				}
			} else { // upper-right to lower-left
				for (int x = startX - 1; x > endX; x--) {
					pathList[index++] = new Point(x, startY);
				}
			}
			pathList[index] = new Point(endX, endY);
			return pathList;
		}

		/*
		 * along diagonal axis (lower-right to upper-left or vice-versa)
		 */
		if (startX == endX) {
			int index = 0;
			if (startY < endY) { // lower-right to upper-left
				for (int y = startY + 1; y < endY; y++) {
					pathList[index++] = new Point(startX, y);
				}
			} else { // upper-left to lower-right
				for (int y = startY - 1; y > endY; y--) {
					pathList[index++] = new Point(startX, y);
				}
			}
			pathList[index] = new Point(endX, endY);
			return pathList;
		}

		/*
		 * along horizontal axis (left to right or vice-versa)
		 */
		if ((startX + startY) == (endX + endY)) {
			int index = 0;
			if (startX < endX) { // left to right
				for (int x = startX + 1, y = startY - 1; x < endX; x++, y--) {
					pathList[index++] = new Point(x, y);
				}
			} else { // Right to left
				for (int x = startX - 1, y = startY + 1; x > endX; x--, y++) {
					pathList[index++] = new Point(x, y);
				}
			}
			pathList[index] = new Point(endX, endY);
			return pathList;
		}

		/*
		 * horizontal-biased (first & second quadrants)
		 */
		if (startX < endX && startY > endY) {
			int doubleDx = Math.abs((endX - startX) + (startY - endY)); // = 2 * dx
			int dy = (endX - startX) + (endY - startY);
			boolean yPositive = dy > 0;
			int thetaX = 3 * doubleDx; // Math.abs(doubleDx);
			int thetaY = 3 * Math.abs(dy);

			int x = startX;
			int y = startY;
			int deviation = 0;
			int index = 0;
			while (x != endX || y != endY) {
				deviation += thetaY;
				if (deviation > doubleDx) {
					if (yPositive) {
						x++; // upper-right: x = x + 1, y stays the same
					} else {
						y--; // lower-right: x stays the same, y = y - 1
					}
					deviation -= thetaX;
				} else {
					x++;
					y--; // right: x = x + 1, y = y - 1
					deviation += thetaY;
				}
				pathList[index++] = new Point(x, y);
			}
			return pathList;
		}

		/*
		 * horizontal-biased (third & fourth quadrants)
		 */
		if (startX > endX && startY < endY) {
			int doubleDx = Math.abs((endX - startX) + (startY - endY)); // = 2 * dx
			int dy = (endX - startX) + (endY - startY);
			boolean yPositive = dy > 0;
			int thetaX = 3 * doubleDx; // Math.abs(doubleDx);
			int thetaY = 3 * Math.abs(dy);

			int x = startX;
			int y = startY;
			int deviation = 0;
			int index = 0;
			while (x != endX || y != endY) {
				deviation += thetaY;
				if (deviation > doubleDx) {
					if (yPositive) {
						y++; // upper-left: x stays the same, y = y + 1
					} else {
						x--; // lower-left: x = x - 1, y stays the same
					}
					deviation -= thetaX;
				} else {
					x--;
					y++; // left: x = x - 1, y = y + 1
					deviation += thetaY;
				}
				pathList[index++] = new Point(x, y);
			}
			return pathList;
		}

		/*
		 * vertical-biased (quadrants 1 & 4) (dy is always positive)
		 */
		if (startX < endX && startY < endY) {
			int doubleDx = (endX - startX) + (startY - endY); // = 2 * dx
			boolean xPositive = doubleDx > 0;
			int thetaX = Math.abs(doubleDx);

			int dy = (endX - startX) + (endY - startY);
			int thetaY = Math.abs(dy);

			int x = startX;
			int y = startY;
			int deviation = 0;
			int index = 0;
			while (x != endX || y != endY) {
				deviation += thetaX;
				if (deviation > 0) {
					// current hex = get DIRS[Xsign][Ysign] hex
					if (xPositive) {
						x++; // upper-right: x = x + 1, y stays the same
					} else {
						y++; // upper-left: x stays the same, y = y + 1
					}
					deviation -= thetaY;
				} else {
					// current hex = get DIRS[-Xsign][Ysign] hex
					if (xPositive) {
						y++; // upper-left: x stays the same, y = y + 1
					} else {
						x++; // upper-right: x = x + 1, y stays the same
					}
					deviation += thetaY;
				}
				pathList[index++] = new Point(x, y);
			}
			return pathList;
		}

		/*
		 * vertical-biased (quadrants 2 & 3) (dy is always negative)
		 */
		if (startX > endX && startY > endY) {
			int doubleDx = (endX - startX) + (startY - endY); // = 2 * dx
			boolean xPositive = doubleDx > 0;
			int thetaX = Math.abs(doubleDx);

			int dy = (endX - startX) + (endY - startY);
			int thetaY = Math.abs(dy);

			int x = startX;
			int y = startY;
			int deviation = 0;
			int index = 0;
			while (x != endX || y != endY) {
				deviation += thetaX;
				if (deviation > 0) {
					// current hex = get DIRS[Xsign][Ysign] hex
					if (xPositive) {
						y--; // lower-right: x stays the same, y = y - 1
					} else {
						x--; // lower-left: x = x - 1, y stays the same
					}
					deviation -= thetaY;
				} else {
					// current hex = get DIRS[-Xsign][Ysign] hex
					if (xPositive) {
						x--; // lower-left: x = x - 1, y stays the same
					} else {
						y--; // lower-right: x stays the same, y = y - 1
					}
					deviation += thetaY;
				}
				pathList[index++] = new Point(x, y);
			}
			return pathList;
		}

		return null;
	}

	/**
	 * Returns the list of hex coordinates for the path between the starting hex and the ending hex. The list does not include
	 * the starting hex coordinates.
	 * 
	 * @param start - the starting hex coordinates
	 * @param end - the ending hex coordinates
	 * @return the array of <code>Point</code>s representing the coordinates for the hexes along the way
	 */
	public static Point[] path(Point start, Point end) {
		return path(start.x, start.y, end.x, end.y);
	}

	/**
	 * Return the list of hex coordinates of the tiles representing the outer perimeter of the circle given the radius. The
	 * number of hexes that form the perimeter of the circle is 6 times the radius.
	 * 
	 * @param radius - the radius of the circle in hex tiles
	 * @return the list of coordinates in an array of <code>Point</code>s
	 */
	public static Point[] getCircleHexes(int radius) {
		if (radius < 1)
			throw new IllegalArgumentException("Invalid radius: " + radius);

		Point[] hexes = new Point[radius * 6];
		int index = 0;
		for (int i = 0, x = -radius, y = 0; i < radius; i++, y++) {
			hexes[index++] = new Point(x, y);
		}
		for (int i = 0, x = -radius, y = radius; i < radius; i++, x++) {
			hexes[index++] = new Point(x, y);
		}
		for (int i = 0, x = 0, y = radius; i < radius; i++, x++, y--) {
			hexes[index++] = new Point(x, y);
		}
		for (int i = 0, x = radius, y = 0; i < radius; i++, y--) {
			hexes[index++] = new Point(x, y);
		}
		for (int i = 0, x = radius, y = -radius; i < radius; i++, x--) {
			hexes[index++] = new Point(x, y);
		}
		for (int i = 0, x = 0, y = -radius; i < radius; i++, x--, y++) {
			hexes[index++] = new Point(x, y);
		}

		return hexes;
	}

}
